package week_03;

import java.util.*;

/**
 * 51. N 皇后
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * 示例 1：
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * <p>
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：[["Q"]]
 */
public class NQueens_2_51 {
    private int[] subset;
    private List<List<String>> ans;
    private int n;
    private boolean[] used;
    private Map<Integer, Boolean> usedIplusJ;
    private Map<Integer, Boolean> usedIminusJ;


    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        subset = new int[n];
        ans = new ArrayList<>();
        used = new boolean[n];
        usedIplusJ = new HashMap<>();
        usedIminusJ = new HashMap<>();
        dfsFind(0);
        return ans;
    }

    public void dfsFind(int row) {
        if (row == n) {
            System.out.println(Arrays.toString(subset));
            addSubAns(subset);
            return;
        }
        // 尝试四个位置
        for (int col = 0; col < n; col++) {
            // i:row j:col
            if(!used[col]){
                if(!usedIplusJ.containsKey(row + col) || !usedIplusJ.get(row + col)){
                    if(!usedIminusJ.containsKey(row-col)|| !usedIminusJ.get(row - col)){
                        used[col] = true;
                        usedIplusJ.put(row + col, true);
                        usedIminusJ.put(row - col, true);
                        subset[row] = col;
                        //System.out.println(row+":"+col);
                        dfsFind(row + 1);
                        subset[row]=0;
                        used[col] = false;
                        usedIplusJ.put(row + col, false);
                        usedIminusJ.put(row - col, false);
                    }
                }
            }
        }
        System.out.println("-----------");
    }

    private void addSubAns(int[] subset) {
        List<String> set = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j == subset[i]) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }

            }
            set.add(sb.toString());
        }
        ans.add(set);
    }

    public static void main(String[] args) {
        NQueens_2_51 test = new NQueens_2_51();
        test.solveNQueens(4);
        test.n = 4;
//        int[] subSet = new int[]{1, 3, 0, 2};
//
//        System.out.println(test.isValid(subSet));
    }
}
